1. Field of the Invention
The present invention relates to an order-relation analyzing apparatus that analyzes order relations among programs executed in parallel, a method, and a computer program product thereof.
2. Description of the Related Art
As a parallel programming environment in a multiprocessor that includes a shared memory, for example, a multi-thread system represented by a POSIX thread is known. In the program described by the multi-thread system, correct descriptions of synchronization relations among a plurality of threads are important. When the synchronization relations among the threads are not described correctly, for example, the following problem is known to occur. The problem is called data races, in which a plurality of threads simultaneously update the same memory region.
To detect the data races, a method of storing partial order relations of sections in a thread is developed, which are executed by using a Logical Vector Clock (vector) and detecting whether the order relations exist among the sections in the threads that have accessed the same address in a memory (For example, refer to U.S. Pat. No. 6,593,940, “Method for finding errors in multithreaded applications”, 2003, hereinafter, “Document 1” and “A Theory of Data Race Detection”, PADTAD-IV 2006, Intel, hereinafter, “Document 2”). The Logical Vector Clock defines logical time with each thread. In the method, an execution state is collected as trace information with each thread being executed, and the Logical Vector Clock, which shows order relations among the threads being executed, is calculated based on the information included in the trace information. In general, in an order relation analysis using the Logical Vector Clock, time viewed from the different threads is stored in each element of the Logical Vector Clock. Accordingly, the Logical Vector Clock that has the same number of elements as the threads to be analyzed needs to be used. Therefore, in conventional technologies such as the Document 1 and Document 2, data size (size of the Logical Vector Clock) for analysis increases in proportion to the number of threads being executed. In a parallel process that is realized in a number of threads, resources required for analysis itself will increase.
In recent years, a method of fixing the number of elements of the Logical Vector Clock to less than the number of threads, so that a plurality of threads can analyze by reusing the number of elements limited to less than the number of threads, while preventing information required for analysis from being omitted as much as possible, is also developed (for example, refer to A. Gidenstam, “Adaptive Plausible Clocks”, Technical Report no. 2003-7, Goterborg University, 2003, hereinafter, “Document 3”).
A technology called NUREV, which is disclosed in the Document 3, intends to share elements among processes that can be simultaneously executed in parallel. In the technology, a process of determining an element to indicate the time of thread is required, whenever a synchronization process occurs, thereby creating a process burden to the determination of element itself. Further, a mapping of elements, which are assigned to each synchronization process, is changed dynamically, thereby increasing the memory capacity for storing the information related to the mapping. A technology called REV, which is also disclosed in the Document 2, determines the elements to be assigned by using a surplus value, which a thread ID is divided by a size of the Logical Vector Clock. Accordingly, such a problem of sharing the same elements in the simultaneously executed threads may occur.